package master;

/**
 * @author chenyw
 * @date 2022/9/8 18:50
 * 寻找两个有序数组的中位数： 二分
 */
public class M4findMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //可以看成是寻找两个有序数组的第k的最小的值，关键思路在于动态的更新k，怎样更新k
        int m = nums1.length;
        int n = nums2.length;
        if ((m + n) % 2 == 1) {
            //总长度如果是奇数
            int midIndex = (m + n) / 2;
            return findK(nums1, nums2, midIndex + 1);
        } else {
            int midIndex1 = (m +n) / 2 - 1, midIndex2 = (m + n) / 2;
            double midNum = (findK(nums1, nums2, midIndex1 + 1) + findK(nums1, nums2, midIndex2 +1)) / 2.0;
            return midNum;
        }
    }

    private int findK(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int index1 = 0, index2 = 0;
//        int kthElement = 0;

        while (true) {
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            //正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 +half, m) - 1;
            int newIndex2 = Math.min(index2 +half, n) - 1;
            if (nums1[newIndex1] <= nums2[newIndex2]) {
                //更新k
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 +1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}
